{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Genetic Mutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小基因变化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 <code>'A'</code>、<code>'C'</code>、<code>'G'</code> 和 <code>'T'</code> 之一。</p>\n",
    "\n",
    "<p>假设我们需要调查从基因序列&nbsp;<code>start</code> 变为 <code>end</code> 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"AACCGGTT\" --&gt; \"AACCGGTA\"</code> 就是一次基因变化。</li>\n",
    "</ul>\n",
    "\n",
    "<p>另有一个基因库 <code>bank</code> 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 <code>bank</code> 中）</p>\n",
    "\n",
    "<p>给你两个基因序列 <code>start</code> 和 <code>end</code> ，以及一个基因库 <code>bank</code> ，请你找出并返回能够使&nbsp;<code>start</code> 变化为 <code>end</code> 所需的最少变化次数。如果无法完成此基因变化，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>注意：起始基因序列&nbsp;<code>start</code> 默认是有效的，但是它并不一定会出现在基因库中。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"AACCGGTT\", end = \"AACCGGTA\", bank = [\"AACCGGTA\"]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"AACCGGTT\", end = \"AAACGGTA\", bank = [\"AACCGGTA\",\"AACCGCTA\",\"AAACGGTA\"]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"AAAAACCC\", end = \"AACCCCCC\", bank = [\"AAAACCCC\",\"AAACCCCC\",\"AACCCCCC\"]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>start.length == 8</code></li>\n",
    "\t<li><code>end.length == 8</code></li>\n",
    "\t<li><code>0 &lt;= bank.length &lt;= 10</code></li>\n",
    "\t<li><code>bank[i].length == 8</code></li>\n",
    "\t<li><code>start</code>、<code>end</code> 和 <code>bank[i]</code> 仅由字符 <code>['A', 'C', 'G', 'T']</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-genetic-mutation](https://leetcode.cn/problems/minimum-genetic-mutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-genetic-mutation](https://leetcode.cn/problems/minimum-genetic-mutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"AACCGGTT\"\\n\"AACCGGTA\"\\n[\"AACCGGTA\"]', '\"AACCGGTT\"\\n\"AAACGGTA\"\\n[\"AACCGGTA\",\"AACCGCTA\",\"AAACGGTA\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        queue = deque([(startGene, 0)])\n",
    "        visited = {startGene}\n",
    "\n",
    "        while queue:\n",
    "            node, steps = queue.popleft()\n",
    "            if node == endGene:\n",
    "                return steps\n",
    "            for c in \"ACGT\":\n",
    "                for i in range(len(node)):\n",
    "                    neighbor = node[:i] + c + node[i + 1:]\n",
    "                    if neighbor not in visited and neighbor in bank:\n",
    "                        visited.add(neighbor)\n",
    "                        queue.append((neighbor, steps + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start, end, bank):\n",
    "        \"\"\"\n",
    "        :type start: str\n",
    "        :type end: str\n",
    "        :type bank: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # valid end gene\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "        \n",
    "        s_list = list()\n",
    "        s_list.append(start)\n",
    "        t_list = list()\n",
    "        t_list.append(0)\n",
    "        while len(s_list) != 0:\n",
    "            s = s_list.pop(0)\n",
    "            last_time = t_list.pop(0)\n",
    "            for gene in bank:\n",
    "                err_cnt = 0\n",
    "                for i in range(len(s)):\n",
    "                    if s[i] != gene[i]:\n",
    "                        err_cnt += 1\n",
    "                        if err_cnt > 1:\n",
    "                            break\n",
    "                else:\n",
    "                    if err_cnt == 1:\n",
    "                        if gene == end:\n",
    "                            return last_time + 1\n",
    "                        else:\n",
    "                            s_list.append(gene)\n",
    "                            t_list.append(last_time + 1)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: 'str', end: 'str', bank: 'List[str]') -> 'int':\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "        q = []\n",
    "        q.append(start)\n",
    "        bank = set(bank)\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        count = 0\n",
    "        while end not in visited:\n",
    "            temp = set()\n",
    "            for word in visited:\n",
    "                ls = list(word)\n",
    "                for g in [\"A\",\"G\",\"C\",\"T\"]:\n",
    "                    i = 0\n",
    "                    while i<len(ls):\n",
    "                        t = ls[:]\n",
    "                        t[i] = g\n",
    "                        t = \"\".join(t)\n",
    "                        if t in bank:\n",
    "                            temp.add(t)\n",
    "                            bank.remove(t)\n",
    "                        i+=1\n",
    "            count += 1\n",
    "            if len(temp) == 0:\n",
    "                return -1\n",
    "            visited = temp\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def minMutation(self, start, end, bank):\n",
    "        \"\"\"\n",
    "        :type start: str\n",
    "        :type end: str\n",
    "        :type bank: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        res = []\n",
    "        dict = set(bank)\n",
    "        dict.add(start)\n",
    "        nodeNeighbors = {}\n",
    "        distances = {}\n",
    "        distances[start] = 0\n",
    "        \n",
    "        self.bfs(start, end, dict, nodeNeighbors, distances)\n",
    "        \n",
    "        if end in distances:\n",
    "            return distances[end]\n",
    "        else:\n",
    "            return -1\n",
    "    \n",
    "    def bfs(self, start, end, dict, nodeNeighbors, distances):\n",
    "        for d in dict:\n",
    "            nodeNeighbors[d] = []\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        \n",
    "        while not q.empty():\n",
    "            count = q.qsize()\n",
    "            foundEnd = False\n",
    "            \n",
    "            for i in range(count):\n",
    "                cur = q.get()\n",
    "                neighbors = self.findNeighbors(cur, dict)\n",
    "                for neighbor in neighbors:\n",
    "                    if neighbor not in distances:\n",
    "                        distances[neighbor] = distances[cur] + 1\n",
    "                        if neighbor == end:\n",
    "                            foundEnd = True\n",
    "                        else:\n",
    "                            q.put(neighbor)\n",
    "            if foundEnd:\n",
    "                break\n",
    "    \n",
    "    def findNeighbors(self, nodeString, dict):\n",
    "        res = []\n",
    "        chs = list(nodeString)\n",
    "        for i in range(len(chs)):\n",
    "            for ch in 'ACGT':\n",
    "                if chs[i] == ch:\n",
    "                    continue\n",
    "                tmp = chs[i]\n",
    "                chs[i] = ch\n",
    "                newString = \"\".join(chs)\n",
    "                if newString in dict:\n",
    "                    res.append(newString)\n",
    "                chs[i] = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        pass\n",
    "\n",
    "        bank = set(bank)\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "\n",
    "        change_map = {\n",
    "            \"A\": \"CGT\",\n",
    "            \"C\": \"AGT\",\n",
    "            \"G\": \"CAT\",\n",
    "            \"T\": \"CGA\",\n",
    "        }\n",
    "\n",
    "        counts = []\n",
    "\n",
    "        def dfs(current, count, current_bank):\n",
    "            # terminator\n",
    "            if current == end:\n",
    "                counts.append(count)\n",
    "                return\n",
    "            if not bank:\n",
    "                return\n",
    "\n",
    "            # process\n",
    "            for i, s in enumerate(current):\n",
    "                for char in change_map[s]:\n",
    "                    new = current[:i] + char + current[i + 1:]\n",
    "                    if new not in current_bank:\n",
    "                        continue\n",
    "                    current_bank.remove(new)\n",
    "                    #print(f\"{i}: {current}-->{new}\")\n",
    "                    # drill down\n",
    "                    dfs(new, count + 1, current_bank)\n",
    "\n",
    "                    # reverse state\n",
    "                    current_bank.add(new)\n",
    "\n",
    "        dfs(start, 0, bank)\n",
    "\n",
    "        return min(counts) if counts else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        front, back, visitor = set([start]), set([end]), set()\n",
    "        cnt = 0\n",
    "        while front:\n",
    "            next_queue = set()\n",
    "            for mutation in front:\n",
    "                visitor.add(mutation)\n",
    "                if mutation in back:\n",
    "                    return cnt\n",
    "                for i in range(len(mutation)):\n",
    "                    for c in \"ACGT\":\n",
    "                        if c != mutation[i]:\n",
    "                            next_mutation = mutation[:i] + c + mutation[i + 1:]\n",
    "                            if next_mutation in bank:\n",
    "                                if next_mutation not in visitor:\n",
    "                                    next_queue.add(next_mutation)\n",
    "            cnt += 1\n",
    "            front = next_queue\n",
    "            if len(front) > len(back):\n",
    "                back, front = front, back\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        bank = set(bank)\n",
    "        if end not in bank: return -1\n",
    "        if start in bank: bank.remove(start)\n",
    "        queue = [start]\n",
    "        step = -1\n",
    "        choice = [\"A\", \"C\", \"G\", \"T\"]\n",
    "        wordLen = len(start)\n",
    "        while len(queue) > 0:\n",
    "            step += 1\n",
    "            newQueue = []\n",
    "            while len(queue) > 0:\n",
    "                word = queue.pop(0)\n",
    "                for i in range(wordLen):\n",
    "                    for j in choice:\n",
    "                        if j == word[i]: continue\n",
    "                        newWord = word[:i] + j + word[i+1:]\n",
    "                        if newWord not in bank: continue\n",
    "                        if newWord == end: \n",
    "                            return step + 1\n",
    "                        newQueue.append(newWord)\n",
    "                        bank.remove(newWord)\n",
    "\n",
    "            queue = newQueue\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\r\n",
    "        from collections import deque\r\n",
    "        bank = set(bank)\r\n",
    "        if end not in bank:\r\n",
    "            return -1\r\n",
    "        visited = set()\r\n",
    "        visited.add(start)\r\n",
    "        mutations = {'A', 'C', 'G', 'T'}\r\n",
    "\r\n",
    "        def oneMuation(cur):\r\n",
    "            for i, val in enumerate(cur):\r\n",
    "                for t in mutations - {val}:\r\n",
    "                    tmp = cur[:i] + t + cur[i+1:]\r\n",
    "                    if tmp in bank:\r\n",
    "                        yield tmp\r\n",
    "\r\n",
    "        q = deque([[start, 0]])\r\n",
    "        while q:\r\n",
    "            cur, res = q.pop()\r\n",
    "            if cur == end:\r\n",
    "                return res\r\n",
    "            for n in oneMuation(cur):\r\n",
    "                if n not in visited:\r\n",
    "                    visited.add(n)\r\n",
    "                    q.appendleft([n, res + 1])\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "        \n",
    "        queue = [(start, 0)]\n",
    "        bank = set(bank)\n",
    "        \n",
    "        while queue:\n",
    "            current_m, step = queue.pop(0)\n",
    "            if current_m == end:\n",
    "                return step\n",
    "            for i in range(len(current_m)):\n",
    "                for m in 'ACGT':\n",
    "                    new_m = current_m[:i] + m +current_m[i+1:]\n",
    "                    if new_m in bank:\n",
    "                        queue.append((new_m, step+1))\n",
    "                        bank.remove(new_m)\n",
    "                        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        hashset, res = set(bank), 0 \n",
    "        leftDeq, rightDeq = deque([start]), deque([end])\n",
    "        leftVis, rightVis = {start}, {end} \n",
    "        if end not in hashset: return -1 \n",
    "\n",
    "        while leftDeq and rightDeq:\n",
    "            if len(leftDeq) > len(rightDeq):\n",
    "                leftDeq, rightDeq = rightDeq, leftDeq\n",
    "                leftVis, rightVis = rightVis, leftVis \n",
    "            res += 1 \n",
    "            for _ in range(len(leftDeq)):\n",
    "                curSeq = leftDeq.popleft()\n",
    "                if curSeq in rightVis: return res -1 \n",
    "\n",
    "                for i in range(len(start)):\n",
    "                    for j in 'ATCG':\n",
    "                        tmpSeq = curSeq[:i] + j + curSeq[i+1:]\n",
    "                        if tmpSeq not in leftVis and tmpSeq in hashset:\n",
    "                            leftVis.add(tmpSeq)\n",
    "                            leftDeq.append(tmpSeq)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        possible_dict = {\n",
    "                        \"A\": \"CGT\",\n",
    "                        \"C\": \"AGT\",\n",
    "                        \"G\": \"ACT\",\n",
    "                        \"T\": \"ACG\"\n",
    "                    }\n",
    "        queue=[(start,0)]\n",
    "        while queue:\n",
    "            # print(\"queue = \", queue)\n",
    "            # 广度优先遍历模板\n",
    "            (word, step)=queue.pop(0)\n",
    "            if word ==end:\n",
    "                return step\n",
    "            \n",
    "            for i, c  in enumerate(word):\n",
    "                \n",
    "                for p in possible_dict[c]:\n",
    "                    # 从第0个位置开始匹配新的字符串\n",
    "                    temp=word[:i]+p+word[i+1:]\n",
    "                    \n",
    "                    # 在bank里面就处理(set中in操作复杂度是0(1))\n",
    "                    if temp in bank: \n",
    "                        # 从bank里移除，避免重复计数\n",
    "                        bank.remove(temp)  \n",
    "                        # 加入队列，步数加1\n",
    "                        queue.append((temp,step+1)) \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check_mutation_sequences(self, gene_to_mutated, gene, end, ret, occurred_genes, counter):\n",
    "        counter += 1\n",
    "        \n",
    "        \n",
    "        if ((ret[0] == None or counter < ret[0]) and gene in gene_to_mutated and gene not in occurred_genes):\n",
    "            mutated_genes = gene_to_mutated[gene]\n",
    "            \n",
    "            \n",
    "            if (end in mutated_genes):\n",
    "                ret[0] = counter + 1\n",
    "                return True\n",
    "            \n",
    "            occurred_genes.add(gene)\n",
    "            \n",
    "            \n",
    "            for mutated_gene in mutated_genes:\n",
    "                self.check_mutation_sequences(gene_to_mutated, mutated_gene, end, ret, occurred_genes, counter)\n",
    "            \n",
    "            occurred_genes.discard(gene)\n",
    "            \n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        gene_to_mutated = collections.defaultdict(lambda: set())\n",
    "        bank.append(start)\n",
    "        end_valid = False if (bank[0] != end) else True\n",
    "        ret = [None]\n",
    "        occurred_genes = set()\n",
    "        \n",
    "        \n",
    "        for a in range(len(bank)):\n",
    "            for b in range(a + 1, len(bank)):\n",
    "                if (not end_valid and bank[b] == end):\n",
    "                    end_valid = True\n",
    "                \n",
    "                different_character_found = False\n",
    "                take_gene = True\n",
    "                    \n",
    "                    \n",
    "                if (len(bank[a]) == len(bank[b])):\n",
    "                    for c in range(len(bank[a])):\n",
    "                        if (bank[a][c] != bank[b][c]):\n",
    "                            if (different_character_found):\n",
    "                                take_gene = False\n",
    "                                break\n",
    "                                \n",
    "                            different_character_found = True\n",
    "                            \n",
    "                \n",
    "                if (take_gene):\n",
    "                    gene_to_mutated[bank[a]].add(bank[b])\n",
    "                    gene_to_mutated[bank[b]].add(bank[a])\n",
    "                    \n",
    "            \n",
    "            if (not end_valid):\n",
    "                return -1\n",
    "            \n",
    "        self.check_mutation_sequences(gene_to_mutated, start, end, ret, occurred_genes, -1)\n",
    "        \n",
    "        if (ret[0] == None):\n",
    "            return -1\n",
    "        else:\n",
    "            return ret[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        s = set()\n",
    "        for b in bank:\n",
    "            s.add(b)\n",
    "        if end not in s: return -1\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        step = 0\n",
    "        while not q.empty():\n",
    "            nowlen = q.qsize()\n",
    "            step += 1\n",
    "            for i in range(nowlen):\n",
    "                f= q.get()\n",
    "                for j in range(8):\n",
    "                    for c in ['A','G','C','T']:\n",
    "                        if c!=f[j]:\n",
    "                            nowg = f[:j]+c+f[j+1:]\n",
    "                            if nowg in s:\n",
    "                                if nowg == end:\n",
    "                                    return step\n",
    "                                s.remove(nowg)\n",
    "                                q.put(nowg)\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        stack = 'ACGT'\n",
    "        queue = collections.deque([(start, 0)])\n",
    "        bank = set(bank)\n",
    "        if start in bank:\n",
    "            bank.remove(start)\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "        while queue:\n",
    "            node, path = queue.pop()\n",
    "            if node == end:\n",
    "                return path\n",
    "            for x,i in enumerate(node):\n",
    "                for j in stack:\n",
    "                    new_node = node[:x] + j + node[x+1:]\n",
    "                    if new_node in bank:\n",
    "                        queue.appendleft((new_node, path+1))\n",
    "                        bank.remove(new_node)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        # if start == end:\n",
    "        #     return 0\n",
    "        # bank = set(bank)\n",
    "        # if end not in bank:\n",
    "        #     return -1\n",
    "        # q = deque([(start, 0)])\n",
    "        # while q:\n",
    "        #     cur, step = q.popleft()\n",
    "        #     for i, x in enumerate(cur):\n",
    "        #         for y in \"ACGT\":\n",
    "        #             if y != x:\n",
    "        #                 nxt = cur[:i] + y + cur[i + 1:]\n",
    "        #                 if nxt in bank:\n",
    "        #                     if nxt == end:\n",
    "        #                         return step + 1\n",
    "        #                     bank.remove(nxt)\n",
    "        #                     q.append((nxt, step + 1))\n",
    "        # return -1\n",
    "        bfs = collections.deque()\n",
    "        bfs.append((start,0))\n",
    "        bankset = set(bank)\n",
    "        while bfs:\n",
    "            gene,step = bfs.popleft()\n",
    "            if gene == end:\n",
    "                return step\n",
    "            for i in range(len(gene)):\n",
    "                for j in \"ACGT\":\n",
    "                    newgene = gene[:i]+j+gene[i+1:]\n",
    "                    if newgene in bankset:\n",
    "                        bfs.append((newgene,step+1))\n",
    "                        bankset.remove(newgene)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque \n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        bank = set(bank)\n",
    "        seen = set()\n",
    "        dq = deque()\n",
    "        res = 0\n",
    "\n",
    "        dq.append(startGene)\n",
    "\n",
    "        while len(dq)!= 0:\n",
    "            # print(dq)\n",
    "            for _ in range(len(dq)):\n",
    "                gene = dq.pop()\n",
    "                seen.add(gene)\n",
    "                if gene == endGene:\n",
    "                    return res\n",
    "                gene = list(gene)\n",
    "\n",
    "\n",
    "                for i in range(len(gene)):\n",
    "                    can_changes =  ['A', 'C', 'G', 'T']\n",
    "                    can_changes.remove(gene[i])\n",
    "                    for change in can_changes:\n",
    "                        old = gene[i]\n",
    "                        gene[i] = change\n",
    "                        new_gene = ''.join(gene)\n",
    "                        gene[i] = old\n",
    "                        # print('new:',new_gene)\n",
    "                        if new_gene in bank and new_gene not in seen:\n",
    "                            dq.appendleft(new_gene)\n",
    "            \n",
    "            res +=1\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        if startGene == endGene:\n",
    "            return 0 \n",
    "        if endGene not in bank:\n",
    "            return -1 \n",
    "        bank = set(bank)\n",
    "        q = collections.deque([startGene])\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur == endGene:\n",
    "                    return step \n",
    "                for i, ch in enumerate(cur):\n",
    "                    for nex in 'ACGT':\n",
    "                        if nex == ch:\n",
    "                            continue \n",
    "                        nexstr = cur[:i] + nex + cur[i + 1:]\n",
    "                        if nexstr in bank:\n",
    "                            q.append(nexstr)\n",
    "                            bank.remove(nexstr)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "idx = 0\n",
    "ans = 0\n",
    "visited = []\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        global idx\n",
    "        global ans\n",
    "        global visited\n",
    "        idx = 0\n",
    "        N, M = 15, 15*15*2+50\n",
    "        he = [-1 for _ in range(N)]\n",
    "        e = [0 for _ in range(M)]\n",
    "        ne = [0 for _ in range(M)]\n",
    "        visited = [0]*(N+1)\n",
    "        if(endGene not in bank):\n",
    "            return -1\n",
    "        l = []\n",
    "        l.append(startGene)\n",
    "        for item in bank:\n",
    "            if(item == endGene):\n",
    "                continue\n",
    "            l.append(item)\n",
    "        l.append(endGene)\n",
    "        n = len(l)\n",
    "        ans = n\n",
    "        def add(a, b):\n",
    "            global idx\n",
    "            e[idx] = b\n",
    "            ne[idx] = he[a]\n",
    "            he[a] = idx\n",
    "            idx += 1\n",
    "        def dfs(u, fa, depth):\n",
    "            global ans\n",
    "            global visited\n",
    "            if(depth >= ans):\n",
    "                return\n",
    "            if(u == n):\n",
    "                ans = depth\n",
    "                return\n",
    "            i = he[u]\n",
    "            while(i!=-1):\n",
    "                j = e[i]\n",
    "                if(visited[j] != 0):\n",
    "                    continue\n",
    "                dfs(j, u, depth+1)\n",
    "                i = ne[i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if(i == j):\n",
    "                    continue\n",
    "                cnt = 0\n",
    "                for k in range(8):\n",
    "                    if(l[i][k] != l[j][k]):\n",
    "                        cnt += 1\n",
    "                    if(cnt > 1):\n",
    "                        break\n",
    "                if(cnt == 1):\n",
    "                    add(i+1, j+1)\n",
    "                    add(j+1, i+1)\n",
    "        \n",
    "        dfs(1, -1, 0)\n",
    "        return -1 if ans == n else ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from typing import List, Optional, Dict, Union\n",
    "\n",
    "INF = sys.maxsize\n",
    "\n",
    "\n",
    "class WeightNode:\n",
    "    def __init__(self, val: int, weight: int, next: Optional['WeightNode'] = None):\n",
    "        self.val: int = val\n",
    "        self.weight: int = weight\n",
    "        self.next: Optional[WeightNode] = next\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"val={self.val}, weight={self.weight}\"\n",
    "\n",
    "\n",
    "class AdjustList:\n",
    "    def __init__(self, vertex_count: int):\n",
    "        self.vertex_count = vertex_count\n",
    "        self.data = [WeightNode(0, -1) for _ in range(vertex_count)]    # 顶点的val保存与之相连的顶点的数量， weight=-1不参与计算\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"vertex_count={self.vertex_count}, node={self.data}\"\n",
    "\n",
    "    def add_edges(self, src: int, dest: int, weight: int) -> None:\n",
    "        \"\"\"在顶点i，j之间加一条边\"\"\"\n",
    "        if src > self.vertex_count or dest > self.vertex_count:  # 顶点越界\n",
    "            return\n",
    "\n",
    "        # 1. src添加一个dest的node, 更新头结点的连接数量\n",
    "        self.add_node(src, dest, weight)\n",
    "        self.data[src].val += 1\n",
    "        if src == dest:  # 环\n",
    "            return\n",
    "\n",
    "        # 2. dest添加一个src的node\n",
    "        self.add_node(dest, src, weight)\n",
    "        self.data[dest].val += 1\n",
    "\n",
    "    def add_node(self, src: int, dest: int, weight: int):\n",
    "        \"\"\"在src顶点添加一个指向dest， weight的节点, 头插\"\"\"\n",
    "        if src > self.vertex_count or dest > self.vertex_count:  # 顶点越界\n",
    "            return\n",
    "        src_node: WeightNode = self.data[src]\n",
    "        node = WeightNode(dest, weight)\n",
    "        node.next = src_node.next\n",
    "        src_node.next = node\n",
    "\n",
    "    def dijkstra(self, src: int) -> Dict[str, List[Union[int, bool]]]:\n",
    "        \"\"\"从src开始，单源最短路径\"\"\"\n",
    "        # 1. 准备三个必要的数组\n",
    "        known: List[int] = [0] * self.vertex_count\n",
    "        cost: List[int] = [INF] * self.vertex_count\n",
    "        path: List[int] = [-1] * self.vertex_count\n",
    "\n",
    "        result: Dict[str, List[Union[int]]] = {'cost': cost, 'path': path, 'known': known}  # 返回的结果\n",
    "\n",
    "        # 2. 从src开始\n",
    "        cost[src], ix = 0, src\n",
    "        while ix != INF:\n",
    "            known[ix] = 1\n",
    "            # 遍历对应的链表，修改对应的cost\n",
    "            node: WeightNode = self.data[ix].next\n",
    "            while node:\n",
    "                dest, weight = node.val, node.weight\n",
    "                if cost[dest] > cost[ix] + weight:\n",
    "                    cost[dest] = cost[ix] + weight\n",
    "                    path[dest] = ix\n",
    "                node = node.next\n",
    "            ix = self.__dijkstra_find_min_weight_idx(known, cost)\n",
    "        return result\n",
    "\n",
    "    def __dijkstra_find_min_weight_idx(self, known: List[bool], costs: List[int]) -> int:\n",
    "        ix = val = INF\n",
    "        for idx, (know, weight) in enumerate(zip(known, costs)):\n",
    "            if not know and weight < val:\n",
    "                val, ix = weight, idx\n",
    "        return ix\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, start: str, end: str, bank: List[str]) -> int:\n",
    "        if end not in bank:\n",
    "            return -1\n",
    "        # 1. 建一个table保存里面字符串与顶点的对应关系\n",
    "        table: Dict[str, int] = {}\n",
    "        for ix, i in enumerate(bank):\n",
    "            table.update({i: ix})\n",
    "        table.update({start: ix+1})\n",
    "\n",
    "        # 2. 建一个图\n",
    "        adj = AdjustList(len(bank) + 1)\n",
    "\n",
    "        # 3. 遍历bank， 只差一个字符的， 按边添加到图里面\n",
    "        bank.append(start)\n",
    "        length = len(bank)\n",
    "        for i in range(0, length):\n",
    "            for j in range(i+1, length):\n",
    "                bi, bj = bank[i], bank[j]\n",
    "                if self.only_one(bank[i], bank[j]):\n",
    "                    adj.add_edges(table[bi], table[bj], 1)\n",
    "        bank.pop()\n",
    "        # 4. dijkstra 找最短路径\n",
    "        result = adj.dijkstra(table[start])\n",
    "        dest: int = table[end]\n",
    "        if not result['known'][dest]:\n",
    "            return -1\n",
    "        return result['cost'][dest]\n",
    "\n",
    "    def only_one(self, s1: str, s2: str) -> bool:\n",
    "        \"\"\"俩字符串只有一个字符不同\"\"\"\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        c = 0\n",
    "        for i, j in zip(s1, s2):\n",
    "            if i != j:\n",
    "                c += 1\n",
    "                if c > 1:\n",
    "                    break\n",
    "        return c <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        if endGene not in bank:\n",
    "            return -1\n",
    "        dic={}\n",
    "        dic[startGene]=0\n",
    "        dic[endGene]=-1\n",
    "        que=deque()\n",
    "        que.append(startGene)\n",
    "        while que:\n",
    "            print(que)\n",
    "            s=que.popleft()\n",
    "            for index,val in enumerate(bank):\n",
    "                if val!=None:\n",
    "                    diff_count = sum(c1 != c2 for c1, c2 in zip(s, val))\n",
    "                    if diff_count==1:\n",
    "                        que.append(val)\n",
    "                        dic[val]=dic[s]+1\n",
    "                        bank[index]=None\n",
    "        return dic[endGene]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "        q = deque([(startGene, 0)])\n",
    "        bankset = set(bank)\n",
    "        while q:\n",
    "            s, cnt = q.popleft()\n",
    "            if s == endGene:\n",
    "                return cnt\n",
    "            # try next permutation\n",
    "            for i in range(len(s)):\n",
    "                for c in 'ACGT':\n",
    "                    next_s = s[:i] + c + s[i + 1:]\n",
    "                    if next_s != s and next_s in bankset:\n",
    "                        q.append((next_s, cnt + 1))\n",
    "                        bankset.remove(next_s)\n",
    "        return -1\n",
    "        \n",
    "        # # handle dup!!!\n",
    "        # index = {}\n",
    "        # bank_new = []\n",
    "        # for s in bank:\n",
    "        #     if s not in index:\n",
    "        #         bank_new.append(s)\n",
    "        #         index[s] = len(index)\n",
    "        # bank = bank_new # !!!\n",
    "        \n",
    "        # if endGene not in index:\n",
    "        #     return -1\n",
    "        \n",
    "        # if startGene not in index: \n",
    "        #     index[startGene] = len(index)\n",
    "        #     bank.append(startGene)\n",
    "\n",
    "        # n = len(bank)\n",
    "        # start = index[startGene]\n",
    "        # target = index[endGene]\n",
    "        # # print(index)\n",
    "        # # print(start, target)\n",
    "\n",
    "        # def distance(a, b):\n",
    "        #     return sum([1 if x != y else 0 for x, y in zip(a, b)])\n",
    "\n",
    "        # # build\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         d = distance(bank[i], bank[j])\n",
    "        #         if d == 1:\n",
    "        #             graph[i].append(j)\n",
    "        #             graph[j].append(i)\n",
    "        \n",
    "        # step = 0\n",
    "        # q = deque([start])\n",
    "        # vis = [False for _ in range(n)]\n",
    "        # vis[start] = True\n",
    "        # while q:\n",
    "        #     # print(q)\n",
    "        #     for _ in range(len(q)):\n",
    "        #         node = q.popleft()\n",
    "        #         if node == target:\n",
    "        #             return step\n",
    "        #         for next_node in graph[node]:\n",
    "        #             if not vis[next_node]:\n",
    "        #                 q.append(next_node)\n",
    "        #                 vis[next_node] = True\n",
    "        #     step += 1\n",
    "            \n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:\n",
    "\n",
    "        bank = set(bank)\n",
    "        if startGene == endGene: return 0\n",
    "        if endGene not in bank: return -1\n",
    "\n",
    "        queue = deque([(startGene,0)])  # 用双端队列记录 (curr_gen, step)，用于BFS\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            for i,x in enumerate(cur):\n",
    "                for y in 'ACGT':\n",
    "                    if x!=y:\n",
    "                        nxt = cur[:i]+y+cur[i+1:]\n",
    "                        if nxt == endGene: return step+1\n",
    "                        if nxt in bank:\n",
    "                            bank.remove(nxt)               # 非常重要！！ 将当前存在的组合删除，防止后续循环遍历\n",
    "                            queue.append((nxt, step+1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        # if startGene==endGene: return 0\n",
    "        # bank = set(bank)\n",
    "        \n",
    "        # if endGene not in bank: return -1\n",
    "\n",
    "        # queue = deque([(startGene,0)])\n",
    "        # while queue:\n",
    "        #     cur,step = queue.popleft()\n",
    "        #     for i,x in enumerate(cur):\n",
    "        #         for y in \"ACGT\":\n",
    "        #             if x!=y:\n",
    "        #                 nxt = cur[:i]+y+cur[i+1:]\n",
    "        #                 if nxt in bank:\n",
    "        #                     if nxt == endGene: \n",
    "        #                         return step+1\n",
    "        #                     bank.remove(nxt) # 将当前存在的组合删除，防止循环遍历？？\n",
    "        #                     queue.append((nxt,step+1))\n",
    "        \n",
    "        # return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
